package _2022.hot100._338_比特位计数;

/**
 * @author： YHSimon
 * @date： 2022-05-31 08:45
 */
public class Solution {

    // O(n) 最低有效位
    public int[] countBits4(int n){
        int[] dp=new int[n+1];
        for(int i=1;i<=n;i++){
            dp[i]=dp[i>>1]+(i&1);
        }
        return dp;
    }


    // O(n) 最高有效位
    public int[] countBits3(int n){
        int[] dp=new int[n+1];
        int highBit=0;
        for(int i=1;i<=n;i++){
            if((i&(i-1))==0){
                highBit=i;
            }
            dp[i]=dp[i-highBit]+1;
        }
        return dp;
    }

    // O(nlogn)
    public int[] countBits2(int n){
        int[] ans=new int[n+1];
        for(int i=0;i<=n;i++){
            int tmp=i;
            int count=0;
            while (tmp!=0){
                if(tmp%2==1){
                    count++;
                }
                tmp/=2;
            }
            ans[i]=count;
        }
        return ans;
    }
    // O(n^2)
    public int[] countBits(int n){
        int[] ans=new int[n+1];
        for(int i=0;i<=n;i++){
            String str = Integer.toBinaryString(i);
            int tmp=0;
            for(int j=0;j<str.length();j++){
                if(str.charAt(j)=='1'){
                    tmp++;
                }
            }
            ans[i]=tmp;
        }
        return ans;
    }
}
